import numpy as np
import textdistance


def get_idf(c, IDF):
    if c in IDF:
        return max(1, IDF[c])
    else:
        return 1

def lcs_skip(s1, s2, IDF):
    """
    基于改进LCS（最长公共子序列）算法计算两个字符串的相似度，引入IDF权重作为不匹配字符的惩罚因子

    参数:
        s1 (str): 待比较的第一个字符串
        s2 (str): 待比较的第二个字符串

    返回:
        float: 计算得到的最大相似度分数
    """
    max_sim = 0  # 用于跟踪计算过程中的最大相似度分数
    # 创建DP表，维度为(len(s1)+1) x (len(s2)+1)，初始值均为0
    # DP表[i][j]表示s1前i个字符与s2前j个字符的相似度分数
    dp = np.zeros((len(s1) + 1, len(s2) + 1))

    # 遍历两个字符串的每个字符位置（DP表从1开始索引）
    for i in range(1, len(s1) + 1):
        for j in range(1, len(s2) + 1):
            # 当前比较的字符（DP表是1索引，字符串是0索引，需-1转换）
            if s1[i - 1] == s2[j - 1]:
                # 字符匹配时，当前相似度为前一个匹配位置的相似度+1（标准LCS递推）
                if not s1[i-1] in u"，。；、；：“”‘’":    # 标点符号不计算
                    dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                # 字符不匹配时，计算不同路径的惩罚后取最大值（至少为0，避免负分）
                # 路径1：跳过s1当前字符，惩罚为s1当前字符的IDF值
                # 路径2：跳过s2当前字符，惩罚为s2当前字符的IDF值
                # 路径3：同时跳过两个字符，惩罚为两个字符IDF的最大值
                dp[i][j] = max(
                    dp[i - 1][j] - get_idf(s1[i - 1], IDF),          # 跳过s1[i-1]的惩罚路径
                    dp[i][j - 1] - get_idf(s2[j - 1], IDF),          # 跳过s2[j-1]的惩罚路径
                    dp[i - 1][j - 1] - max(get_idf(s1[i - 1], IDF), get_idf(s2[j - 1], IDF)),  # 同时跳过两个字符的惩罚路径
                    0  # 确保相似度分数不为负
                )
            # 更新最大相似度分数（取当前DP值与历史最大值的较大者）
            max_sim = max(max_sim, dp[i][j])

    # 返回计算得到的最大相似度分数
    return max_sim


def get_lcs_naive(s1, s2):
    sim_gram = textdistance.lcsstr.similarity(s1, s2)
    s1_ngram = get_ngram(s1, sim_gram)
    s2_ngram = get_ngram(s2, sim_gram)
    sim_span = s1_ngram.intersection(s2_ngram)
    # assert len(sim_span) == 1, sim_span
    return list(sim_span)


def get_ngram(s, n):
    result = set()
    for i in range(0, len(s) - n + 1):
        result.add(s[i:i + n])
    return result
